package 力扣日常刷题.木22一月.第09天0117;

import java.util.Arrays;

/**
 * @author 帅小伙
 * @date 2022/1/17
 * @description
 */
public class Demo11动态规划中等下降路径最小和 {


    public static void main(String[] args) {
        Demo11动态规划中等下降路径最小和 test = new Demo11动态规划中等下降路径最小和();

        test.minFallingPathSum(new int[][]{{-48}});
    }

    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        int[] dp = new int[n + 2];
        int[] tdp = new int[n + 2];
        Arrays.fill(dp, Integer.MAX_VALUE);
        Arrays.fill(tdp, Integer.MAX_VALUE);
        for (int i = 0; i < n; i++) {
            dp[i + 1] = matrix[0][i];
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n; j++) {
                tdp[j + 1] = Math.min(Math.min(dp[j], dp[j + 1]), dp[j + 2]) + matrix[i][j];
            }
            System.arraycopy(tdp, 0, dp, 0, n+2);
        }
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < dp.length; i++) {
            ans = Math.min(ans, dp[i]);
        }
        return ans;
    }
}
